package com.engine.cn.leetcode.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 注意栈和树结合的情况
 * 在面试中，二叉树的前序、中序、后序遍历（尤其是非递归实现）是非常高频的考点，但实际场景的考察侧重点有所不同。以下是具体分析：
 */
public class OrderIterative {

    /**
     * 前序遍历
     *
     * @param root root节点
     * @return List<String>
     */
    public static List<String> preorderTraversal(BinaryTree root) {
        List<String> result = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        if (root == null) {
            return result;
        }

        stack.push(root);
        //前序遍历
        while (!stack.isEmpty()) {
            BinaryTree current = stack.pop();
            result.add(current.getVal());
            if (current.getRight() != null) {
                stack.push(current.getRight());
            }
            if (current.getLeft() != null) {
                stack.push(current.getLeft());
            }
        }

        return result;
    }

    /**
     * 中序遍历，中序遍历是最常考的
     * current 负责向左深入，stack 负责回溯和转向右子树。
     *
     * @param root root节点
     * @return List<String>
     */
    public static List<String> inorderTraversal(BinaryTree root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree current = root;
        while (current != null || !stack.isEmpty()) {
            //1.压入所有左子节点
            while (current != null) {
                //先压入父，再压入子
                stack.push(current);
                current = current.getLeft();
            }
            //2.压完左子树后弹出栈顶并访问
            current = stack.pop();
            result.add(current.getVal());

            //3.转入右子树(此刻，左边已经遍历完了)
            current = current.getRight();
        }
        return result;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree("A");
        tree.left = new BinaryTree("B");
        tree.right = new BinaryTree("C");
        tree.left.left = new BinaryTree("D");
        tree.left.right = new BinaryTree("E");
        tree.right.left = new BinaryTree("F");
        tree.right.right = new BinaryTree("G");
        List<String> preorderTraversal = preorderTraversal(tree);
        System.out.println("preorderTraversal==>" + preorderTraversal);
        List<String> inorderTraversal = inorderTraversal(tree);
        System.out.println("inorderTraversal==>" + inorderTraversal);
    }
}
